package com.wjw.java.collection.list_;

import java.util.LinkedList;

/**
 * LinkedList是List接口的实现类
 * -------------------------------------------------------------------------
 * LinkedList细节：
 * 1.LinkedList是有序的,可以存储重复元素的集合
 * 2.LinkedList允许存储null,且多个
 * 3.LinkedList是线程不安全的
 * -------------------------------------------------------------------------
 * 底层源码分析：
 * 1.LinkedList底层维护了一个双向链表
 * 2.LinkedList中维护了两个属性,first和last分别指向首节点和尾结点
 * 3.每个节点都是一个(Node对象),里面又维护了prev、next、item三个属性,
 *   其中prev指向上一个节点,next指向下一个节点,最终实现双向链表
 * 4.LinkedList的元素添加和删除,不是通过数组完成的,效率高
 * -------------------------------------------------------------------------
 *              next    -->     next    -->     next
 * first  -->   item            item            item    <--  last
 *              prev    <--     prev    <--     prev
 * -------------------------------------------------------------------------
 * ArrayList和LinkedList对比
 * 1.ArrayList底层是可变数组,增删效率较低(数组扩容),改查效率较高
 * 2.LinkedList底层是双向链表,增删效率较高,通过链表追加,改查效率较低
 * 3.增删较多时使用LinkedList,改查较多时使用ArrayList
 * -------------------------------------------------------------------------
 */
public class Detail_LinkedList {

    public static void main(String[] args) {
        double_linked_list();
        method_linked_list();
    }

    //1.模拟一个简单的双向链表代码
    public static void double_linked_list(){
        //1.声明三个节点
        Node n1 = new Node("N1");
        Node n2 = new Node("N2");
        Node n3 = new Node("N3");

        //2.连接三个节点,形成双向链表
        //n1 --> n2 --> n3
        n1.next = n2;
        n2.next = n3;
        //n3 --> n2 --> n1
        n3.prev = n2;
        n2.prev = n1;

        //3.
        Node first = n1;//让first引用指向n1,表示双向链表的首节点
        Node last = n3;//让last引用指向n3,表示双向链表的尾节点

        //4.演示,从头到尾进行遍历
        System.out.println("1.----->双向链表:从前往后进行遍历");
        while (true){
            if(first == null){
                break;
            }
            System.out.println(first);
            first = first.next;
        }

        //5.演示,从尾到头进行遍历
        System.out.println("2.双向链表:从后往前进行遍历<-----");
        while (true){
            if(last == null){
                break;
            }
            System.out.println(last);
            last = last.prev;
        }

        //6.添加节点
        System.out.println("3.双向链表:在n2和n3直接添加一个节点a");
        Node a = new Node("A");
        a.prev = n2;
        a.next = n3;
        n2.next = a;
        n3.prev = a;

        //7.从头到尾进行遍历
        System.out.println("4.----->双向链表:从前往后再次进行遍历");
        first = n1;//让first引用再次指向n1,表示双向链表的首节点
        while (true){
            if(first == null){
                break;
            }
            System.out.println(first);
            first = first.next;
        }

        //8.从尾到头进行遍历
        last = n3;//让last引用再次指向n3,表示双向链表的尾节点
        System.out.println("5.双向链表:从后往前再次进行遍历<-----");
        while (true){
            if(last == null){
                break;
            }
            System.out.println(last);
            last = last.prev;
        }
    }

    //2.LinkedList方法
    public static void method_linked_list(){
        LinkedList linkedList = new LinkedList();
        //1.add()添加元素、addFirst()首部插入、addLast()尾部插入
        linkedList.addFirst(1);
        linkedList.addLast(1000);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);

        //2.get()获取元素
        System.out.println(linkedList.get(0));//1

        //3.remove()删除元素、removeFirst()首部删除、removeLast()尾部删除
        linkedList.remove();//默认删除第一个元素
        linkedList.removeFirst();
        linkedList.removeLast();
        System.out.println(linkedList);//[2, 3, 4]
        linkedList.remove(1);//删除索引为1的元素,索引从0开始
        System.out.println(linkedList);//[2, 4]

        //4.set()修改xx索引位置的元素
        linkedList.set(0,999);
        System.out.println(linkedList);//[999, 4]

        //5.遍历LinkedList可以使用Iterator、for循环、foreach
    }
}
//定义一个Node对象,Node对象表示双向链表的一个节点
class Node{
    public Object item;//存放数据
    public Node next;//指向下一个节点
    public Node prev;//指向上一个节点
    public Node(Object name) {
        this.item = name;
    }
    @Override
    public String toString() {
        return "Node{" +
                "item=" + item +
                '}';
    }
}